#include "../../include/common.h"

/*
    递归实现
*/
void PostOrderTraverse_Recursion(BiTree T){
    if (T) {
        PostOrderTraverse_Recursion(T->lchild);      //访问该结点的左孩子
        PostOrderTraverse_Recursion(T->rchild);      //访问该结点的右孩子
        PrintBiT(T);                               //调用操作结点数据的函数方法
    }
    //如果结点为空，返回上一层
    return;
}

/*********************************************************/
/*
    迭代实现：借助栈
*/
int top = -1;
//定义一个顺序栈
BiTree  a[20];

void Push(BiTree* a,BiTree elem)
{
     a[++top]=elem;
}

void Pop()
{
    if (top==-1) {
        return ;
   }
    top--;
}

BiTree GetTop(BiTree*a){
    return a[top];
}


void PostOrderTraverse_Iterative(BiTree Tree)
{
    //临时指针
    BiTree r, p = Tree;
    while (p || top!=-1) {
        //一直取栈顶元素，且不能为NULL
        if (p){
            //将该结点的进栈，如果没有左孩子，NULL进栈
            Push(a, p);
            p = p->lchild;
        }
        else {
            //取栈顶元素
            p=GetTop(a);
            if (p->rchild && p->rchild != r)    // 有右子树就先访问右子树
                p = p->rchild;
            else {
                Pop();
                PrintBiT(p);
                r = p;
                p = NULL;
            }
        }
    }
}




void run(char* param[]) {
    if (strcmp(param[1], "late") != 0)
        return ;
    BiTree Tree;
    CreateBiTree(&Tree);
    printf("后序遍历: \n");
    if (strcmp(param[2], "recursion") == 0)
        PostOrderTraverse_Recursion(Tree);
    else
        PostOrderTraverse_Iterative(Tree);

   printf("\n\n");
}